﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RPGProject.Data_Structures
{
    /// <summary>
    /// A class for holding a set of a data. Supports only insertion of single elements.
    /// </summary>
    /// <typeparam name="TData"></typeparam>
    class Set<TData> : IEnumerable<TData>
    {
        /// <summary>
        /// Size of the set
        /// </summary>
        private int size;
        public int Size
        {
            get { return this.size; }
        }
        /// <summary>
        /// The first node.
        /// </summary>
        private SetNode top;
        /// <summary>
        /// Constructs a set
        /// </summary>
        public Set()
        {
            this.size = 0;
        }
        /// <summary>
        /// Constructs a set from a list of parameters.
        /// </summary>
        /// <param name="data"></param>
        public Set(TData[] data)
        {
            foreach (TData d in data)
            {
                this.Insert(d);
            }
        }
        /// <summary>
        /// Inserts the data into the set.
        /// </summary>
        /// <param name="data"></param>
        public void Insert(TData data)
        {
            if (this.top == null)
            {
                this.top = new SetNode();
                this.top.data = data;
                this.size++;
            }
            else
            {
                if (this.top.Insert(data))
                    this.size++;
            }
        }
        /// <summary>
        /// Inserts the data into the set.
        /// </summary>
        /// <param name="data"></param>
        public void Insert(Set<TData> set)
        {
            if (set.Size <= 0)
                return;
            foreach (TData data in set)
            {
                this.Insert(data);
            }
        }
        /// <summary>
        /// Operator version of insert.
        /// </summary>
        /// <param name="rhs"></param>
        /// <param name="lhs"></param>
        /// <returns></returns>
        public static Set<TData> operator +(Set<TData> rhs, TData lhs)
        {
            rhs.Insert(lhs);
            return rhs;
        }
        /// <summary>
        /// Operator version of insert.
        /// </summary>
        /// <param name="rhs"></param>
        /// <param name="lhs"></param>
        /// <returns></returns>
        public static Set<TData> operator +(Set<TData> lhs, Set<TData> rhs)
        {
            lhs.Insert(rhs);
            return rhs;
        }
        /// <summary>
        /// Indexer to see if the element is in the set.
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool this[TData data]
        {
            get
            {
                if (this.top == null)
                    return false;
                else
                    return this.top.Find(data);
            }
        }

        /// <summary>
        /// A helper class
        /// </summary>
        private class SetNode
        {
            // Holder for the data and the left and right nodes
            public TData data;
            public SetNode left;
            public SetNode right;
            /// <summary>
            /// Finds the data specified in the array, and returns if its there or not.
            /// </summary>
            /// <param name="data"></param>
            /// <returns></returns>
            public bool Find(TData data)
            {
                if (this.data.Equals(data))
                    return true;
                else
                    if (this.data.GetHashCode() < data.GetHashCode())
                        if (this.left == null)
                            return false;
                        else
                            return this.left.Find(data);
                    else
                        if (this.right == null)
                            return false;
                        else
                            return this.right.Find(data);
            }
            /// <summary>
            /// Inserts the data if its not already in the array.
            /// </summary>
            /// <param name="data"></param>
            /// <returns></returns>
            public bool Insert(TData data)
            {
                if (this.data.Equals(data))
                    return false;
                else
                {
                    if (this.data.GetHashCode() < data.GetHashCode())
                    {
                        if (this.left != null)
                        {
                            return this.left.Insert(data);
                        }
                        else
                        {
                            this.left = new SetNode();
                            this.left.data = data;
                            return true;
                        }
                    }
                    else
                    {
                        if (this.right != null)
                        {
                            return this.right.Insert(data);
                        }
                        else
                        {
                            this.right = new SetNode();
                            this.right.data = data;
                            return true;
                        }
                    }
                }
            }
        }
        /// <summary>
        /// Returns an enumerator for foreach statements.
        /// </summary>
        /// <returns></returns>
        public IEnumerator<TData> GetEnumerator()
        {
            // stack for determining to return left or right
            Vector<Iterated> leftOrRight = new Vector<Iterated>();
            Vector<SetNode> nodes = new Vector<SetNode>();
            nodes.Push(this.top);
            leftOrRight.Push(Iterated.NONE);
            while (leftOrRight.Count > 0)
            {
                switch (leftOrRight.Peek())
                {
                    case Iterated.NONE:
                        yield return nodes.Peek().data;
                        leftOrRight.Pop();
                        leftOrRight.Push(Iterated.LEFT);
                        break;
                    case Iterated.LEFT:
                        leftOrRight.Pop();
                        leftOrRight.Push(Iterated.RIGHT);
                        if (nodes.Peek().left != null)
                        {
                            nodes.Push(nodes.Peek().left);
                            leftOrRight.Push(Iterated.NONE);
                        }
                        break;
                    case Iterated.RIGHT:
                        leftOrRight.Pop();
                        leftOrRight.Push(Iterated.BOTH);
                        if (nodes.Peek().right != null)
                        {
                            nodes.Push(nodes.Peek().right);
                            leftOrRight.Push(Iterated.NONE);
                        }
                        break;
                    case Iterated.BOTH:
                        nodes.Pop();
                        leftOrRight.Pop();
                        break;
                }
            }
        }
        public override string ToString()
        {
            String ret = "{ ";
            foreach(TData d in this)
            {
                ret += d.ToString() + " ";
            }
            ret += "}";
            return ret;
        }
        /// <summary>
        /// Returns an enumerator for foreach statements.
        /// </summary>
        /// <returns></returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
        private enum Iterated
        {
            NONE,
            LEFT,
            RIGHT,
            BOTH
        }
    }
}
